---
title: Умножение матриц в параллельных потоках
description: Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков Java Stream. Возьмём оптимизированный вариант алгоритма на трёх вложенных...
sections: [Многопоточность,Вложенные циклы,Сравнение алгоритмов]
tags: [java,потоки,массивы,многомерные массивы,матрицы,строки,циклы]
canonical_url: /ru/2022/02/08/matrix-multiplication-parallel-streams.html
url_translated: /en/2022/02/09/matrix-multiplication-parallel-streams.html
title_translated: Matrix multiplication in parallel streams
date: 2022.02.08
---

Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков Java Stream. Возьмём
*оптимизированный вариант* алгоритма на трёх вложенных циклах и заменим внешний цикл на поток. Сравним
время работы двух алгоритмов.

Строки результирующей матрицы обрабатываем в параллельном режиме, а каждую строку заполняем слоями.
За счёт параллельного использования кеша среды выполнения на многоядерных машинах время вычислений
можно сократить более чем в два раза. Для проверки возьмём две прямоугольные матрицы: {`L×M`} и {`M×N`}.

*Дальнейшая оптимизация: [Алгоритм Винограда — Штрассена]({{ '/ru/2022/02/10/winograd-strassen-algorithm.html' | relative_url }}).*

## Параллельный поток {#parallel-stream}

Строки первой матрицы `L` обходим в параллельном режиме. Внутри каждого потока два вложенных цикла:
по *общей стороне* двух матриц `M` и по колонкам второй матрицы `N`. Обработка строк результирующей
матрицы происходит независимо друг от друга в параллельных потоках.

```java
/**
 * @param l строки матрицы 'a'
 * @param m колонки матрицы 'a'
 *          и строки матрицы 'b'
 * @param n колонки матрицы 'b'
 * @param a первая матрица 'l×m'
 * @param b вторая матрица 'm×n'
 * @return результирующая матрица 'l×n'
 */
public static int[][] parallelMatrixMultiplication(int l, int m, int n, int[][] a, int[][] b) {
    // результирующая матрица
    int[][] c = new int[l][n];
    // обходим индексы строк матрицы 'a' в параллельном режиме
    IntStream.range(0, l).parallel().forEach(i -> {
        // обходим индексы общей стороны двух матриц:
        // колонок матрицы 'a' и строк матрицы 'b'
        for (int k = 0; k < m; k++)
            // обходим индексы колонок матрицы 'b'
            for (int j = 0; j < n; j++)
                // сумма произведений элементов i-ой строки
                // матрицы 'a' и j-ой колонки матрицы 'b'
                c[i][j] += a[i][k] * b[k][j];
    });
    return c;
}
```

## Три вложенных цикла {#three-nested-loops}

Возьмём оптимизированный вариант алгоритма, который лучше прочих использует кеш среды выполнения.
Внешний цикл обходит строки первой матрицы `L`, далее идёт цикл по *общей стороне* двух матриц `M`
и за ним цикл по колонкам второй матрицы `N`. Запись в результирующую матрицу происходит построчно,
а каждая строка заполняется слоями.

```java
/**
 * @param l строки матрицы 'a'
 * @param m колонки матрицы 'a'
 *          и строки матрицы 'b'
 * @param n колонки матрицы 'b'
 * @param a первая матрица 'l×m'
 * @param b вторая матрица 'm×n'
 * @return результирующая матрица 'l×n'
 */
public static int[][] sequentialMatrixMultiplication(int l, int m, int n, int[][] a, int[][] b) {
    // результирующая матрица
    int[][] c = new int[l][n];
    // обходим индексы строк матрицы 'a'
    for (int i = 0; i < l; i++)
        // обходим индексы общей стороны двух матриц:
        // колонок матрицы 'a' и строк матрицы 'b'
        for (int k = 0; k < m; k++)
            // обходим индексы колонок матрицы 'b'
            for (int j = 0; j < n; j++)
                // сумма произведений элементов i-ой строки
                // матрицы 'a' и j-ой колонки матрицы 'b'
                c[i][j] += a[i][k] * b[k][j];
    return c;
}
```

## Тестирование {#testing}

Для проверки возьмём две матрицы: `A=[900×1000]` и `B=[1000×750]`, заполненные случайными числами.
Сначала сравниваем между собой корректность реализации двух алгоритмов — произведения матриц
должны совпадать. Затем выполняем каждый метод по 10 раз и подсчитываем среднее время выполнения.

```java
// запускаем программу и выводим результат
public static void main(String[] args) {
    // входящие данные
    int l = 900, m = 1000, n = 750, steps = 10;
    int[][] a = randomMatrix(l, m), b = randomMatrix(m, n);
    // произведения матриц
    int[][] c1 = parallelMatrixMultiplication(l, m, n, a, b);
    int[][] c2 = sequentialMatrixMultiplication(l, m, n, a, b);
    // проверяем корректность результатов
    System.out.println("Результаты совпадают: " + Arrays.deepEquals(c1, c2));
    // замеряем время работы двух методов
    benchmark("Потоки", steps, () -> {
        int[][] c = parallelMatrixMultiplication(l, m, n, a, b);
        if (!Arrays.deepEquals(c, c1)) System.out.print("ошибка");
    });
    benchmark("Циклы", steps, () -> {
        int[][] c = sequentialMatrixMultiplication(l, m, n, a, b);
        if (!Arrays.deepEquals(c, c2)) System.out.print("ошибка");
    });
}
```

{% capture collapsed_md %}
```java
// вспомогательный метод, возвращает матрицу указанного размера
private static int[][] randomMatrix(int row, int col) {
    int[][] matrix = new int[row][col];
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            matrix[i][j] = (int) (Math.random() * row * col);
    return matrix;
}
```
```java
// вспомогательный метод для замера времени работы переданного кода
private static void benchmark(String title, int steps, Runnable runnable) {
    long time, avg = 0;
    System.out.print(title);
    for (int i = 0; i < steps; i++) {
        time = System.currentTimeMillis();
        runnable.run();
        time = System.currentTimeMillis() - time;
        // время выполнения одного шага
        System.out.print(" | " + time);
        avg += time;
    }
    // среднее время выполнения
    System.out.println(" || " + (avg / steps));
}
```
{% endcapture %}
{%- include collapsed_block.html summary="Вспомогательные методы" content=collapsed_md -%}

Вывод зависит от среды выполнения, время в миллисекундах:

```
Результаты совпадают: true
Потоки | 113 | 144 | 117 | 114 | 114 | 117 | 120 | 125 | 111 | 113 || 118
Циклы | 1357 | 530 | 551 | 569 | 535 | 538 | 525 | 517 | 518 | 514 || 615
```

## Сравнение алгоритмов {#comparing-algorithms}

На восьмиядерном компьютере Linux x64 создаём для тестов виртуальную машину Windows x64. При
прочих равных условиях в настройках меняем количество процессоров. Запускаем вышеописанный
тест 100 раз вместо 10 — получаем сводную таблицу результатов. Время в миллисекундах.

```
   ЦПУ |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |
-------|-----|-----|-----|-----|-----|-----|-----|-----|
Потоки | 522 | 276 | 179 | 154 | 128 | 112 | 110 |  93 |
Циклы  | 519 | 603 | 583 | 571 | 545 | 571 | 559 | 467 |
```

Результаты: при большом количестве процессоров в системе многопоточный алгоритм отрабатывает
заметно быстрее, чем три вложенных цикла. Время вычислений можно сократить более чем в два раза.

Все описанные выше методы, включая свёрнутые блоки, можно поместить в одном классе.

{% capture collapsed_md %}
```java
import java.util.Arrays;
import java.util.stream.IntStream;
```
{% endcapture %}
{%- include collapsed_block.html summary="Необходимые импорты" content=collapsed_md -%}
